package com.yanceysong.codetop.s81_s90;

public class S87_Mid_198_打家劫舍 {

    /**
     * .S87_Mid_198_打家劫舍
     * .<p>
     * .<a href="https://leetcode.cn/problems/house-robber/">...</a>
     * .<p>
     * .你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
     * .如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
     * .<p>
     * .给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
     * .<p>
     * .示例 1：
     * .<p>
     * .输入：[1,2,3,1]
     * .输出：4
     * .解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     * .     偷窃到的最高金额 = 1 + 3 = 4 。
     * .<p>
     * .示例 2：
     * .<p>
     * .输入：[2,7,9,3,1]
     * .输出：12
     * .解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     * .     偷窃到的最高金额 = 2 + 9 + 1 = 12 。
     * .<p>
     * .提示：
     * .<p>
     * .1 <= nums.length <= 100
     * .0 <= nums[i] <= 400
     * .<p>
     * .核心标签：动态规划、数组
     * .<p>
     * .解题思路：
     * .这是一个经典的动态规划问题，关键在于理解"不能偷相邻房屋"的约束条件。
     * .<p>
     * .状态定义：
     * .dp[i] 表示偷窃前 i+1 个房屋（从第0个到第i个）能够获得的最高金额
     * .<p>
     * .状态转移方程：
     * .dp[i] = max(dp[i-1], dp[i-2] + nums[i])
     * .<p>
     * .解释：对于第 i 个房屋，有两种选择：
     * .1. 不偷第 i 个房屋：最高金额 = dp[i-1]（前 i 个房屋的最高金额）
     * .2. 偷第 i 个房屋：最高金额 = dp[i-2] + nums[i]（前 i-1 个房屋的最高金额 + 第 i 个房屋的金额）
     * .   注意：如果偷第 i 个房屋，就不能偷第 i-1 个房屋，所以是 dp[i-2]
     * .<p>
     * .初始化：
     * .- dp[0] = nums[0]（只有一个房屋，直接偷）
     * .- dp[1] = max(nums[0], nums[1])（两个房屋，选金额大的偷）
     * .<p>
     * .关键洞察：
     * .1. 这是一个无后效性问题，当前状态只依赖于前两个状态
     * .2. 不能偷相邻房屋 ≠ 必须隔一个偷一个（可能隔多个）
     * .3. 可以优化空间复杂度到 O(1)，只需保存前两个状态
     * .4. 贪心算法不适用：不能简单地选择所有奇数或偶数位置
     * .<p>
     * .ASCII 图解示例 1：
     * .<p>
     * .输入：nums = [1, 2, 3, 1]
     * .<p>
     * .房屋示意图：
     * .<p>
     * .索引:    0    1    2    3
     * .       ┌───┬───┬───┬───┐
     * .金额:  │ 1 │ 2 │ 3 │ 1 │
     * .       └───┴───┴───┴───┘
     * .<p>
     * .动态规划过程：
     * .<p>
     * .初始化：
     * .dp[0] = 1  （只偷第0个房屋）
     * .dp[1] = max(1, 2) = 2  （偷第0或第1个房屋，选金额大的）
     * .<p>
     * .填充 dp[2]：
     * .选择1：不偷房屋2 → dp[1] = 2
     * .选择2：偷房屋2 → dp[0] + nums[2] = 1 + 3 = 4
     * .dp[2] = max(2, 4) = 4  ✓ 选择偷房屋2
     * .<p>
     * .填充 dp[3]：
     * .选择1：不偷房屋3 → dp[2] = 4
     * .选择2：偷房屋3 → dp[1] + nums[3] = 2 + 1 = 3
     * .dp[3] = max(4, 3) = 4  ✓ 选择不偷房屋3
     * .<p>
     * .DP 数组变化过程：
     * .<p>
     * .i=0:  [1, ?, ?, ?]  ← 初始化 dp[0] = 1
     * .i=1:  [1, 2, ?, ?]  ← 初始化 dp[1] = max(1,2) = 2
     * .i=2:  [1, 2, 4, ?]  ← dp[2] = max(2, 1+3) = 4
     * .i=3:  [1, 2, 4, 4]  ← dp[3] = max(4, 2+1) = 4
     * .<p>
     * .最优方案：偷房屋 0 和 2，金额 = 1 + 3 = 4
     * .<p>
     * .决策树示意：
     * .<p>
     * .                   起点(0)
     * .                  /      \
     * .             偷房屋0(1)   不偷房屋0(0)
     * .             /      \         /      \
     * .        不偷1(1)  偷1(2)   不偷1(0)  偷1(2)
     * .         /   \     /  \      /  \     /  \
     * .       偷2  不偷  偷2 不偷   偷2 不偷  偷2 不偷
     * .       (4)  (1)  (5) (2)   (3) (0)  (5) (2)
     * .<p>
     * .═══════════════════════════════════════════════════════════════
     * .<p>
     * .示例 2：nums = [2, 7, 9, 3, 1]
     * .<p>
     * .房屋示意图：
     * .<p>
     * .索引:    0    1    2    3    4
     * .       ┌───┬───┬───┬───┬───┐
     * .金额:  │ 2 │ 7 │ 9 │ 3 │ 1 │
     * .       └───┴───┴───┴───┴───┘
     * .<p>
     * .动态规划过程：
     * .<p>
     * .初始化：
     * .dp[0] = 2
     * .dp[1] = max(2, 7) = 7
     * .<p>
     * .填充过程：
     * .dp[2] = max(dp[1], dp[0] + nums[2])
     * .      = max(7, 2 + 9)
     * .      = max(7, 11) = 11  ✓ 偷房屋2
     * .<p>
     * .dp[3] = max(dp[2], dp[1] + nums[3])
     * .      = max(11, 7 + 3)
     * .      = max(11, 10) = 11  ✓ 不偷房屋3
     * .<p>
     * .dp[4] = max(dp[3], dp[2] + nums[4])
     * .      = max(11, 11 + 1)
     * .      = max(11, 12) = 12  ✓ 偷房屋4
     * .<p>
     * .DP 数组变化过程：
     * .<p>
     * .i=0:  [2, ?, ?, ?, ?]
     * .i=1:  [2, 7, ?, ?, ?]
     * .i=2:  [2, 7, 11, ?, ?]  ← max(7, 2+9) = 11
     * .i=3:  [2, 7, 11, 11, ?]  ← max(11, 7+3) = 11
     * .i=4:  [2, 7, 11, 11, 12]  ← max(11, 11+1) = 12
     * .<p>
     * .最优方案：偷房屋 0, 2, 4，金额 = 2 + 9 + 1 = 12
     * .<p>
     * .可视化偷窃方案：
     * .<p>
     * .索引:    0    1    2    3    4
     * .       ┌───┬───┬───┬───┬───┐
     * .金额:  │ 2 │ 7 │ 9 │ 3 │ 1 │
     * .       └───┴───┴───┴───┴───┘
     * .         ✓   ✗   ✓   ✗   ✓
     * .        偷       偷       偷
     * .<p>
     * .总金额: 2 + 9 + 1 = 12
     * .<p>
     * .═══════════════════════════════════════════════════════════════
     * .<p>
     * .为什么贪心算法不适用？
     * .<p>
     * .反例：nums = [2, 1, 1, 2]
     * .<p>
     * .贪心（选所有偶数位置）：2 + 1 = 3
     * .贪心（选所有奇数位置）：1 + 2 = 3
     * .最优解（动态规划）：2 + 2 = 4  ✓
     * .<p>
     * .索引:    0    1    2    3
     * .       ┌───┬───┬───┬───┐
     * .金额:  │ 2 │ 1 │ 1 │ 2 │
     * .       └───┴───┴───┴───┘
     * .         ✓   ✗   ✗   ✓
     * .<p>
     * .时间复杂度：O(n)
     * .- 需要遍历一次数组，计算每个位置的最大金额
     * .<p>
     * .空间复杂度：O(n)
     * .- 需要 n 大小的 dp 数组
     * .- 可以优化到 O(1)，只保存前两个状态（prev2, prev1）
     */
    public int rob(int[] nums) {
        // 边界条件：空数组
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int houseCount = nums.length;

        // 边界条件：只有一个房屋
        if (houseCount == 1) {
            return nums[0];
        }

        // 创建 dp 数组，dp[i] 表示偷窃前 i+1 个房屋能获得的最高金额
        int[] dp = new int[houseCount];

        // 初始化：第一个房屋，直接偷
        dp[0] = nums[0];

        // 初始化：前两个房屋，选金额大的偷
        dp[1] = Math.max(nums[0], nums[1]);

        // 动态规划：从第3个房屋开始
        for (int i = 2; i < houseCount; i++) {
            // 选择1：不偷当前房屋，金额 = dp[i-1]
            int notRobCurrent = dp[i - 1];

            // 选择2：偷当前房屋，金额 = dp[i-2] + nums[i]
            int robCurrent = dp[i - 2] + nums[i];

            // 取两种选择中的最大值
            dp[i] = Math.max(notRobCurrent, robCurrent);
        }

        // 返回偷窃所有房屋能获得的最高金额
        return dp[houseCount - 1];
    }

    public static void main(String[] args) {
        S87_Mid_198_打家劫舍 solution = new S87_Mid_198_打家劫舍();

        System.out.println("=== 打家劫舍测试开始 ===");

        // 测试1: 示例1
        System.out.println("\n--- 测试1: 示例1 [1,2,3,1] ---");
        testCase1(solution);

        // 测试2: 示例2
        System.out.println("\n--- 测试2: 示例2 [2,7,9,3,1] ---");
        testCase2(solution);

        // 测试3: 单个房屋
        System.out.println("\n--- 测试3: 单个房屋 [5] ---");
        testSingleHouse(solution);

        // 测试4: 两个房屋
        System.out.println("\n--- 测试4: 两个房屋 [1,2] ---");
        testTwoHouses(solution);

        // 测试5: 所有金额相同
        System.out.println("\n--- 测试5: 所有金额相同 [5,5,5,5] ---");
        testSameAmounts(solution);

        // 测试6: 递增序列
        System.out.println("\n--- 测试6: 递增序列 [1,2,3,4,5] ---");
        testIncreasingSequence(solution);

        // 测试7: 递减序列
        System.out.println("\n--- 测试7: 递减序列 [5,4,3,2,1] ---");
        testDecreasingSequence(solution);

        // 测试8: 贪心反例
        System.out.println("\n--- 测试8: 贪心反例 [2,1,1,2] ---");
        testGreedyCounterExample(solution);

        // 测试9: 包含0的数组
        System.out.println("\n--- 测试9: 包含0 [2,0,0,3,0,5] ---");
        testWithZeros(solution);

        // 测试10: 较大数组
        System.out.println("\n--- 测试10: 较大数组 [5,3,4,11,2] ---");
        testLargerArray(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * .测试1: 示例1
     * .输入：[1,2,3,1]
     * .期望输出：4
     */
    private static void testCase1(S87_Mid_198_打家劫舍 solution) {
        int[] nums = {1, 2, 3, 1};
        System.out.println("输入: [1, 2, 3, 1]");

        int result = solution.rob(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 4");
        System.out.println("解释: 偷窃房屋 0 (金额=1) 和房屋 2 (金额=3)，总金额 = 1 + 3 = 4");
        assert result == 4 : "结果应为 4";
        System.out.println("✓ 测试1通过");
    }

    /**
     * .测试2: 示例2
     * .输入：[2,7,9,3,1]
     * .期望输出：12
     */
    private static void testCase2(S87_Mid_198_打家劫舍 solution) {
        int[] nums = {2, 7, 9, 3, 1};
        System.out.println("输入: [2, 7, 9, 3, 1]");

        int result = solution.rob(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 12");
        System.out.println("解释: 偷窃房屋 0 (金额=2)、房屋 2 (金额=9) 和房屋 4 (金额=1)，总金额 = 2 + 9 + 1 = 12");
        assert result == 12 : "结果应为 12";
        System.out.println("✓ 测试2通过");
    }

    /**
     * .测试3: 单个房屋
     * .输入：[5]
     * .期望输出：5
     */
    private static void testSingleHouse(S87_Mid_198_打家劫舍 solution) {
        int[] nums = {5};
        System.out.println("输入: [5]");

        int result = solution.rob(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 5");
        assert result == 5 : "单个房屋应返回该房屋的金额";
        System.out.println("✓ 测试3通过");
    }

    /**
     * .测试4: 两个房屋
     * .输入：[1,2]
     * .期望输出：2
     */
    private static void testTwoHouses(S87_Mid_198_打家劫舍 solution) {
        int[] nums = {1, 2};
        System.out.println("输入: [1, 2]");

        int result = solution.rob(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 2");
        System.out.println("解释: 两个房屋只能偷一个，选金额大的");
        assert result == 2 : "两个房屋应选金额大的";
        System.out.println("✓ 测试4通过");
    }

    /**
     * .测试5: 所有金额相同
     * .输入：[5,5,5,5]
     * .期望输出：10
     */
    private static void testSameAmounts(S87_Mid_198_打家劫舍 solution) {
        int[] nums = {5, 5, 5, 5};
        System.out.println("输入: [5, 5, 5, 5]");

        int result = solution.rob(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 10");
        System.out.println("解释: 偷窃房屋 0 和房屋 2，总金额 = 5 + 5 = 10");
        assert result == 10 : "结果应为 10";
        System.out.println("✓ 测试5通过");
    }

    /**
     * .测试6: 递增序列
     * .输入：[1,2,3,4,5]
     * .期望输出：9
     */
    private static void testIncreasingSequence(S87_Mid_198_打家劫舍 solution) {
        int[] nums = {1, 2, 3, 4, 5};
        System.out.println("输入: [1, 2, 3, 4, 5]");

        int result = solution.rob(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 9");
        System.out.println("解释: 偷窃房屋 0 (金额=1)、房屋 2 (金额=3) 和房屋 4 (金额=5)，总金额 = 1 + 3 + 5 = 9");
        assert result == 9 : "结果应为 9";
        System.out.println("✓ 测试6通过");
    }

    /**
     * .测试7: 递减序列
     * .输入：[5,4,3,2,1]
     * .期望输出：9
     */
    private static void testDecreasingSequence(S87_Mid_198_打家劫舍 solution) {
        int[] nums = {5, 4, 3, 2, 1};
        System.out.println("输入: [5, 4, 3, 2, 1]");

        int result = solution.rob(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 9");
        System.out.println("解释: 偷窃房屋 0 (金额=5)、房屋 2 (金额=3) 和房屋 4 (金额=1)，总金额 = 5 + 3 + 1 = 9");
        assert result == 9 : "结果应为 9";
        System.out.println("✓ 测试7通过");
    }

    /**
     * .测试8: 贪心反例
     * .输入：[2,1,1,2]
     * .期望输出：4
     * .说明：这个例子说明贪心算法（选所有偶数或奇数位置）不适用
     */
    private static void testGreedyCounterExample(S87_Mid_198_打家劫舍 solution) {
        int[] nums = {2, 1, 1, 2};
        System.out.println("输入: [2, 1, 1, 2]");

        int result = solution.rob(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 4");
        System.out.println("解释: 偷窃房屋 0 (金额=2) 和房屋 3 (金额=2)，总金额 = 2 + 2 = 4");
        System.out.println("注意: 如果用贪心选所有偶数位置，只能得到 2+1=3");
        assert result == 4 : "结果应为 4";
        System.out.println("✓ 测试8通过");
    }

    /**
     * .测试9: 包含0的数组
     * .输入：[2,0,0,3,0,5]
     * .期望输出：7
     */
    private static void testWithZeros(S87_Mid_198_打家劫舍 solution) {
        int[] nums = {2, 0, 0, 3, 0, 5};
        System.out.println("输入: [2, 0, 0, 3, 0, 5]");

        int result = solution.rob(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 7");
        System.out.println("解释: 偷窃房屋 0 (金额=2) 和房屋 5 (金额=5)，总金额 = 2 + 5 = 7");
        assert result == 7 : "结果应为 7";
        System.out.println("✓ 测试9通过");
    }

    /**
     * .测试10: 较大数组
     * .输入：[5,3,4,11,2]
     * .期望输出：16
     */
    private static void testLargerArray(S87_Mid_198_打家劫舍 solution) {
        int[] nums = {5, 3, 4, 11, 2};
        System.out.println("输入: [5, 3, 4, 11, 2]");

        int result = solution.rob(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 16");
        System.out.println("解释: 偷窃房屋 0 (金额=5) 和房屋 3 (金额=11)，总金额 = 5 + 11 = 16");
        assert result == 16 : "结果应为 16";
        System.out.println("✓ 测试10通过");
    }
}
